//2018
//2.明码 
//
//#include <bits/stdc++.h>
//using namespace std;
//char a[32]; 
//
//void Printf(char i)
//{
//	while(i)
//	{
//		char n=i%2;
//		if(n)cout<<'*';
//		else cout<<' '; 
//		i/=2;
//	}
//}
//int main()
//{
//	
//		for(int j=0;j<32;j++)
//		{
//			cin>>a[j];
//		}
//	
//	
//		for(int j=0;j<32;j++)
//		{
//			Printf(a[j]);
//			if(j%2==0)cout<<endl;
//		}
//	
//	return 0;
//} 

//3.乘积尾零 
//#include <bits/stdc++.h>
//using namespace std;
//
//int a[10][10];
//int n,m;
//int getn(int i)
//{
//
//	int cnt=0;
//	while(i)
//	{
//		if(i%2==0)
//		cnt++;
//		else break;
//		i/=2;
//	}	
//	return cnt;
//}
//int getm(int i)
//{
//	int cnt=0;
//	while(i)
//	{
//		if(i%5==0)
//		cnt++;
//		else break;	
//		i/=5;
//	}	
//	return cnt;
//} 
//int main()
//{
//	
//	for(int i=0;i<10;i++)
//	{
//		for(int j=0;j<10;j++)
//		{
//			cin>>a[i][j];
//			n+=getn(a[i][j]);
//			m+=getm(a[i][j]);
//		}
//	}
//	cout<<min(n,m);
//	return 0;
//}


//2021蓝桥杯b组省赛 

//1.卡片 ans-3181 percent:100% 
//memset只能用来初始化字符数组，char a[]，memset(a,'*",10)，对前10个字符初始化为'*'。而切忌不可以用于初始化其他类型数组，可能会报错。其他类型数组要用for来初始化 ，谨慎使用memset初始化.他初始化默认的都是字符的 
//例如：memset(a, '3',sizeof(a));//sizeof算的就是字节数，他的赋值是给每个字节都赋值称'3'的.
//#include <bits/stdc++.h>
//using namespace std;
//int a[10]={0};
//bool f(int n)
//{
//	while(n)
//	{
//		int val=n%10;
//		if(a[val]==0)return false;
//		else a[val]--;
//		n/=10; 
//	}
//	return true;
//}
//int main()
//{
//	for(int i=0;i<10;i++)a[i]=2021;
//	
//	for(int i=1;i<=20210;i++)
//	{
//		if(!f(i))
//		{
//			cout<<i-1;
//			break;
//		}
//	}
//	return 0;
//}

////2.直线 -set的妙用，直线的定义 y =kx +b =(deta y /deta x)*x +b;先确定k，再确定b. 
//#include <iostream>
//#include <set>
//#include <bits/stdc++.h>
//using namespace std;
//typedef pair<int, int> PII;
//typedef pair<pair<int, int>, int> PIII;
//int gcd(int a, int b)//除去了最大公约数之后，两个数直接就没有除了1以外的因素了。因为最大公约数=所有公因数的相乘 
//{
//	if (b == 0)return a;
//	return gcd(b, a % b);
//}
//int main()
//{
//	set<PIII> st;
//	for (int x1 =1; x1 <= 20; x1++)
//	{
//		for (int y1 = 1; y1 <= 21; y1++)
//		{
//			for (int x2 = 1; x2 <= 20;x2++)
//			{
//				for (int y2 = 1; y2 <= 21; y2++)
//				{
//					int x = x2 - x1;
//					int y = y2 - y1;
//
//					int d = gcd(x, y);
//					if (d)
//					{
//						x /= d;
//						y /= d;
//						int c = y1 * x - x1 * y;//截距 
//						PII p(x, y);
//						PIII pp(p, c);
//						st.insert(pp);
//					}
//				}
//			}
//
//		}
//	}
//	cout << st.size();
//	return 0;
//}



//3.货物摆放 -set的妙用 + 理由逆向思维减少一层循环 
//
//#include <bits/stdc++.h>
//using namespace std;
//typedef long long ll;
//ll n;
//int main()
//{
//	n=2021041820210418;
//	int cnt=0;
//	for(ll a=1;a<=sqrt(n);a++)//找组合 
//	{
//		if(n%a==0)
//		{
//			for(ll b=a;b<=sqrt(n/a);b++)//从a开始表示组合，需要自己算出组合含有的cnt的个数。从1开始表示排列 ，排列只需要直接cnt++;即可 
//			{
//				if((n/a)%b==0)
//				{
//					ll c=n/a/b;
//						if(a*b*c==n) 
//						{
//							set<ll> st;
//							st.insert(a);
//							st.insert(b);
//							st.insert(c);
//							if(st.size()==1)cnt++;
//							else if(st.size()==2)cnt+=3;
//							else if(st.size()==3)cnt+=6;
//						
//						}
//				}
//			}
//		}
//	}
//	cout<<cnt;
//	
//	return 0;
//}


////4.路径 floyd最短路算法 不断取(i,j)【这里是已知的、一开始的、存在的其中一条边的长度】 与(i,k) + (k,j)之间的边的长度的最小值 。即可得到最短边
////关于调试的技巧：可以每部分用cout<<1打印区分开，如果某部分后面的打印不出来，则表明该部分可能会有问题。 
//#include  <bits/stdc++.h>
//using namespace std;
//typedef long long ll;
//ll edge[2022][2022];//表示i与j之间的联结矩阵。edge[i][j]是等于edge[j][i]的.只需要考虑上半部分即可. 
//int gcd(int a,int b)
//{
//	if(b==0)return a;
//
//	return gcd(b,a%b);
//}
//int lcm(int a,int b)
//{
//	
//	int c=a*b;
//
//	return c/gcd(a,b);
//}
//int main()
//{
//	for(int i=1;i<=2021;i++)
//	{
//		for(int j=1;j<=2021;j++)
//		{
//			if(abs(i-j)<=21)edge[i][j]=lcm(i,j);//初始化i到j的已经存在的一条已知边的长度 
//			else edge[i][j]=INT_MAX;//表示达不到 
//		}
//	}	
//
//	for(int k=1;k<=2021;k++)
//	{
//		for(int i=1;i<=2021;i++)
//		{
//			for(int j=i+1;j<=2021;j++)
//			{
//				edge[i][j]=min(edge[i][j],edge[i][k]+edge[k][j]);
//			}
//		}
//	}
//	cout<<edge[1][2021];
//	return 0;
//}


////5.空间
//#include <bits/stdc++.h>
//using namespace std;
//int main()
//{
//  // 请在此输入您的代码
//  long long ret=256*1024*1024/4;//注意要小心爆了范围，最好能化简的化简。 
//  printf("%lld",ret);
//  return 0;
//}


//6.砝码称重 
//法1.dfs深搜+回溯    50% - 需要优化  (可以采取剪枝、记忆化搜索 或者是把dfs换成DP) 
//#include <bits/stdc++.h>
//using namespace std;
//const int N=1e2+10;
//set<int> st;
//int a[N];
//int n;
//void dfs(int idex,int sum)//不能重复+求组合 
//{
//	if(sum>0)
//	st.insert(sum);
//	// set<int>::iterator it=st.begin();//记录在测试完后要把调试的信息注释或者去掉再交
//	// while(it!=st.end())
//	// {
//	// 	cout<<*it<<' ';
//	// 	it++;
//	// }
//	// cout<<endl;
//	
//	for(int i=idex;i<=n;i++)
//	{
//		dfs(i+1,sum+a[i]);
//		dfs(i+1,sum-a[i]);
//	}
//}
//int main()
//{
//
//	cin>>n;
//	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
//	
//	dfs(1,0);
//	cout<<st.size();
//	return 0;
//}

////法2.DP
//#include <bits/stdc++.h>
//using namespace std;
//const int N=1e3;
//int dp[N][N];//表示在前i个物品情况下，j大小的背包，装的物品的价值(这里的价值是重量) 
//int weigh[N];
//int main()
//{	
//	int n;
//	cin>>n;
//	int sum=0;
//	for(int i=1;i<=n;i++)
//	{
//		scanf("%d",&weigh[i]);	
//		sum+=weigh[i];
//	}
//	
//	for(int i=1;i<=n;i++)//表示物品的下标 
//	{
//		for(int j=sum;j>=1;j--)//表示背包的大小
//		{
//			dp[i][j]=max(dp[i-1][j],dp[i][j-weigh[i]]+weigh[i]);
//		} 
//	}
//	set<int> st;
//	for(int i=1;i<=n;i++)//表示物品的下标 
//	{
//		for(int j=sum;j>=1;j--)//表示背包的大小
//		{
//			st.insert(dp[i][j]);
//		} 
//	}
//	cout<<st.size();
//	return 0;
//} 





//7.时间显示
//#include <bits/stdc++.h>
//using namespace std;
//typedef long long ll;
//ll a[3];//秒:分:时 
//int main()
//{
//	ll n;
//	cin>>n;
//	n/=1000;
//	int i=0;
//	while(n)
//	{
//		if(i==0||i==1)
//		{
//			a[i++]=n%60;//取余数 
//			n/=60;
//		}
//		else if(i==2)
//		{
//			a[i++]=n%24;
//			n/=24;
//		}
//		else if(i==3)break;
//	}
//	reverse(a,a+3);//左闭右开
//	for(int i=0;i<3;i++)
//	{
//		if(i==0||i==1)
//		{
//			if(a[i]<10)
//			{
//				cout<<0<<a[i]<<':';
//			}
//			else cout<<a[i]<<':';
//		}
//		else 
//		{
//			if(a[i]<10)
//			{
//				cout<<0<<a[i];
//			}
//			else cout<<a[i];
//		}
//	}
//	return 0;
//}


//8.杨辉三角 
//法1.excel打表+word去表格+devc++遍历数组 30% 
//#include <bits/stdc++.h>
//using namespace std;
//int a[]=
//{
//	1,																						
//1,	1,	
//1,	2,	1,	
//1,	3,	3,	1,	
//1,	4	,6	,4,	1,	
//1,	5	,10,	10,	5,	1,	
//1,	6,	15,	20,	15,	6,	1,
//1,	7,	21,	35,	35,	21,	7,	1,	
//1,	8,	28,	56,	70,	56,	28,	8,	1,	
//1,	9,	36,	84,	126,	126,	84,	36,	9,	1,	
//1,	10,	45,	120,	210,	252,	210,	120,	45,	10,	1,
//1,	11,	55,	165,	330,	462,	462,	330,	165,	55,	11,	1,
//1,	12,	66,	220,	495,	792,	924,	792,	495,	220,	66,	12,	1,
//1,	13,	78,	286,	715,	1287,	1716,	1716,	1287,	715,	286,	78,	13,	1,
//1,	14,	91	,364,	1001,	2002,	3003,	3432,	3003,	2002,	1001,	364,	91,	14,	1,
//1,	15,	105,	455,	1365,	3003	,5005,	6435,	6435,	5005,	3003,	1365,	455,	105,	15,	1,			
//1	,16,	120,	560,	1820,	4368,	8008,	11440,	12870,	11440,	8008,	4368,	1820,	560,	120,	16,	1,
//1,	17,	136,	680,	2380,	6188,	12376,	19448,	24310,	24310,	19448,	12376,	6188,	2380,	680,	136,	17,	1,
//1,	18,	153,	816,	3060,	8568,	18564,	31824,	43758,	48620,	43758,	31824,	18564,	8568,	3060,	816,	153,	18,	1,
//1,	19,	171,	969,	3876,	11628,	27132,	50388,	75582,	92378,	92378,	75582,	50388,	27132,	11628,	3876,	969,	171,	19,	1,
//1,	20,	190	,1140,	4845,	15504	,38760	,77520,	125970	,167960,	184756,	167960,	125970,	77520	,38760,	15504	,4845,	1140	,190	,20	,1,
//1,	21,	210,	1330,	5985,	20349,	54264	,116280	,203490,	293930,	352716,	352716,	293930	,203490	,116280,	54264,	20349	,5985,	1330,	210,	21	,1	,
//1,	22,	231,	1540,	7315,	26334,	74613	,170544	,319770	,497420	,646646	,705432,	646646,	497420,	319770,	170544,	74613,	26334,	7315	,1540	,231,	22,	1,
//1,	23	,253,	1771,	8855,	33649,	100947,	245157,	490314,	817190,	1144066,	1352078,	1352078,	1144066,	817190,	490314,	245157	,100947	,33649,	8855,	1771	,253	,23	,1,
//1,	24,	276,	2024,	10626,	42504,	134596,	346104,	735471,	1307504	,1961256	,2496144,	2704156	,2496144,	1961256	,1307504,	735471	,346104,	134596,	42504	,10626,	2024,	276	,24	,1
//
//
//};
//int main()
//{
//	int n;
//	cin>>n;
//	for(int i=0;i<sizeof(a)/sizeof(a[0]);i++)
//	{
//		if(a[i]==n)
//		{
//			cout<<i+1;
//			break;
//		}
//	}
//	
//	return 0;
//}

////法2.用数组生成杨辉三角 -30%
//#include <iostream>
//using namespace std;
//const int N=30;
//typedef long long ll;
//ll a[N+1][N+1];
//int flag=0;
//int main()
//{
//	int n;
//	cin>>n;
//	a[1][1]=1;
//	for(int i=2;i<=N;i++)
//	{
//		for(int j=1;j<=N;j++)
//		{
//			a[i][j]=a[i-1][j-1]+a[i-1][j];
//		}
//	}
//
//	int idex=0;
//
//	for(int i=1;i<=N;i++)
//	{
//		for(int j=1;j<=N;j++)
//		{
//			idex++;
//
//			if(a[i][j]==n)
//			{
//				cout<<idex;
//				return 0;
//			}
//			
//			
//			if(a[i][j]<=0)
//			{
//				i++;
//				j=1;
//			}
//			
//		}
//	}
//	cout<<"no find";
//	return 0;
//} 

////9.双向排序
//
//#include <iostream>
//#include <bits/stdc++.h>
//using namespace std;
//int main()
//{
//	//栈区开辟空间，先开辟的空间地址高
//	int a = 10;
//	int b = 20;
//	cout << &a << endl;
//	cout << &b << endl;
//
//	//堆区开辟空间，先开辟的空间地址低
//	int* c = (int*)malloc(sizeof(int)* 10);
//	int* d = (int*)malloc(sizeof(int)* 10);
//	cout << c << endl;
//	cout << d << endl;
//	return 0;
//}
//


//10.括号序列















